package com.mlming.simpledb.backend.dm.pageIndex;

import com.mlming.simpledb.backend.dm.pageCache.PageCache;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

/**
 * 页面索引: **方便上层模块进行插入操作,无需遍历所有的页来寻找足够空间插入的页**
 * 注意: **这个索引和我们之前学过的数据库的索引不是一个东西, 之前我们学的索引是: 以索引列值为key然后加速查询操作**
 *
 * 这里的索引, **并非是用于加速查询操作的,而是用于加速在插入时寻找足够空闲空间的页面的**,
 *
 * 整体原理:
 * 把所有的页按照其空闲空间的大小, 将同一个档次的空闲空间大小的那些页面放在一起,
 * 方便上层模块在插入时,无需遍历所有的页来寻找足够空间插入的页,
 * 只需要通过一定规则的计算, 判断当前插入的数据需要的空闲空间的档次,
 * 然后去对应的空闲空间档次的那些页面中随便取出一个即可
 */
public class PageIndex {
    // 以 页面大小(8K) 划分为40分的结果, 作为计量单位
    private static final int INTERVALS_NO = 40;
    private static final int THRESHOLD = PageCache.PAGE_SIZE / INTERVALS_NO;

    private Lock lock; // 锁
    private List<PageInfo>[] lists; // List数组, 每一个List里面存的是同一个空闲空间档次的页面s

    public PageIndex() {
        lock = new ReentrantLock();
        lists = new List[INTERVALS_NO + 1]; // 由之前的分档次的分析可知,我们要把==页面大小的,放到40号里面, 所以需要41个List
        for (int i = 0; i < INTERVALS_NO+1; i ++) {
            lists[i] = new ArrayList<>();
        }
    }

    // 把一个页面插入到索引里(即: 给该页面插入到其对应的空闲空间档次的List里面)
    // **页面所属的List的下标的计算方式是:  该页面的空闲空间 / THRESHOLD(会向下取整)**
    public void add(int pgno, int freeSpace) {
        lock.lock();// 因为要对共享索引进行操作, 所以要加锁
        try {
            // 1) 通过下标计算方式: 该页面的空闲空间 / THRESHOLD(会向下取整), 得到该页面应该分配到的List下标
            int index = freeSpace / THRESHOLD;
            // 2) 插入到对应的List里面去
            lists[index].add(new PageInfo(pgno, freeSpace));
        } finally {
            lock.unlock();
        }
    }

    // 用于上层模块要插入时, 把插入所需空间传入, 我们通过之前说的规则, 从对应的档次的List中取出一个满足其所需空间的页面返回
    // 如何利用上述索引来找到空闲空间满足插入空间的页面?
    // 下标计算方式:  插入所需的空闲空间 / THRESHOLD + 1 , 然后去对应下标的List里面随意取(取头元素)即可
    public PageInfo select(int insertNeedSpace) {
        lock.lock();// 因为要对共享索引进行操作, 所以要加锁
        try {
            // 1) 通过上述下标计算方式, 计算出满足该插入空间的页面所在的List的下标
            int index = insertNeedSpace / THRESHOLD + 1;
            // 2) 如果下标大于了40, 说明数组会越界,
            //    逻辑上说明该插入空间已经>一个页面的大小了, 不符合我们之前规定的**一个数据不能分页存储**,
            //    所以返回null来告知上层模块
            if(index > INTERVALS_NO) return null;
            // 3) 如果对应的List为空, 说明当前区间没有页面,
            //    那么秉承着向上取整来获得足够空间的原则, 我们接着向上找List, 直到不为空(要注意越界判断)
            while (index <= INTERVALS_NO && lists[index].size() == 0) {
                index++;
            }
            // 此时如果是越界了, 因为之前已经判断过 插入数据过大的情况了, 所以这里返回null
            // 表明的是: 当前所有已经存在的页, 无法满足插入空间
            if(index > INTERVALS_NO) return null;
            // 4) 返回对应List的头元素, 同时remove掉
            // 这里注意:
            // 被选择的页，会直接从 PageIndex 中移除，这意味着，同一个页面是不允许并发写的。
            // **在上层模块使用完这个页面后，需要将该页面再调用一下add方法来重新插入PageIndex**
            return lists[index].remove(0);
        } finally {
            lock.unlock();;
        }
    }
}
